/**
 * 与LeetCode329类似，要求任意递增路径的方案数
 * 记忆化搜索DP即可。
 * 
 */
using llt = long long;
llt const MOD = 1E9 + 7;
llt const None = 0x7F2F3F4F5F6F7F8F;

class Solution {

using vi = vector<llt>;

int N, M;
vector<vi> D;

public:
    int countPaths(vector<vector<int>>& grid)  {
        static int const DR[] = {-1, 1, 0, 0};
        static int const DC[] = {0, 0, -1, 1};

        N = grid.size();
        M = grid[0].size();
        D.assign(N, vi(M, None));

        function<llt(int, int)> __dfs = [&](int x, int y)->llt{
            if(None != D[x][y]) return D[x][y];
            
            int ans = 1;
            for(int nr,nc,i=0;i<4;++i){
                nr = x + DR[i];
                nc = y + DC[i];
                if(0 <= nr and nr < N and 0 <= nc and nc < M and grid[x][y] < grid[nr][nc]){
                    ans = (ans + __dfs(nr, nc)) % MOD;
                }
            }
            return D[x][y] = ans;
        };

        int ans = 0;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            ans = (ans + __dfs(i, j)) % MOD;
        }
        return ans;
    }
};
